#include <iostream>
#include <cassert>
using namespace std;
template <class T>
class Queue {
	struct ListNode {
		T data;
		ListNode* pre;
		ListNode* next;
	};
	ListNode* m_list;
	int m_size;
public:
	Queue() {
		m_list = new ListNode;
		m_list->pre = m_list;
		m_list->next = m_list;
		m_size = 0;
	}
	Queue(T data) : Queue() {
		ListNode* node = new ListNode;
		node->data = data;
		node->pre = m_list->pre;
		node->next = m_list;
		m_list->pre->next = node;
		m_list->pre = node;
		m_size++;
	}
	~Queue() {
		ListNode* it = m_list->next;
		ListNode* pr = nullptr;
		while (it != m_list) {
			pr = it;
			it = it->next;
			delete pr;
		}
		delete it;
		m_size = -1;
	}
public:
	void push(T data) { // 入队
		ListNode* node = new ListNode;
		node->data = data;
		node->pre = m_list->pre;
		node->next = m_list;
		m_list->pre->next = node;
		m_list->pre = node;
		m_size++;
	}
	void pop() { // 出队
		if (empty()) return;
		ListNode* current = m_list->next;
		current->next->pre = m_list;
		m_list->next = current->next;
		delete current;
		m_size--;
	}
	void clear() {
		ListNode* it = m_list->next;
		ListNode* pr = nullptr;
		while (it != m_list) {
			pr = it;
			it = it->next;
			delete pr;
		}
		m_list->next = m_list;
		m_list->pre = m_list;
		m_size = 0;
	}
public:
	bool empty() {
		return m_list->next == m_list;
	}
	T getTop() {
		return m_list->next->data;
	}
	int size() {
		return m_size;
	}
	T operator[](int pos) {
		assert(pos >= 0 && pos < m_size);
		ListNode* current = m_list->next;
		while (pos--) {
			current = current->next;
		}
		return current->data;
	}
};
int main() {
	Queue<int> queue(1);
	queue.push(2);
	queue.push(3);
	queue.push(4);
	queue.push(5);
	queue.push(6);
	queue.clear();
	for (int i = 0; i < queue.size(); ++i) {
		cout << queue[i] << " ";
	}
	return 0;
}